Arrays are a form of data structure that typically hold entries of the same data type. Each entry in an array will typically have a specific value, from a range of values associated with a data type, and will be retrievable by indexing a search key into the array.
Arrays often store a large number of entries, and where an array is stored in computer readable memory, as the number of entries increases, so too does the memory resources allocated to store those entries.
One type of array that often holds a large number of entries, and thus occupies substantial memory resources, includes route tables for performing a look up of a route associated with an Internet Protocol (IP) address. Such route tables are typically stored in memory on board Internet routers that forward IP packets to a destination given by a destination IP address field in a packet header. As will be understood, an IP address comprises binary 1's and 0's which the Internet router “looks up” in its route table to determine which adjacent router or network is able to carry the IP packet through to its destination.
Since the structure of the Internet, and in turn IP addresses, is hierarchical, a subset of the IP address, the left-most bits called the prefix, uniquely identifies a subnetwork of many computers or a subnetwork of further smaller networks themselves connected to many computers. The problem of finding a route then consists of matching the most specific or longest prefix in the route table to the destination IP address found in a packet. Such a look up is often referred to as “longest prefix matching” and the associated route tables as “longest prefix match tables”.
By way of example, a 32-bit IP (IP version 4) address of 162.122.14.20 might be the IP address of a particular computer on the Internet (expressed as four 8-bit numbers in dot notation), but any IP packet addressed to 162.122.14.* (that is, addresses 162.122.14.1 through 162.122.14.255) would reach the sub-network of 255 computers of which 162.122.14.20 is a member. That is, the 24-bit address prefix of 162.122.14.* uniquely locates this sub-network. We might also find, however, that any IP address prefixed by the 8-bit prefix 162.*.*.* locates all computers in a broad geographical region.
One popular data structure for a route table facilitating longest-prefix matching is a multi-way or radix trie. A radix trie consists of a collection of tables containing table entries that are indexed by a multi-bit part of an IP address (“the look up key”). Each table entry either points to next-hop route data (that is, the result of a route), or points to another table—a subtable that covers routes of prefixes longer than that of the parent table. A lookup is typically performed by indexing a first level table with a fixed number of address bits, and then continuing to index lower level subtables with subsequent bits of the address until the lookup finds next-hop data or fails.
In practice, the lookup key may not be split into digits of equal radix or size. Typically, the first digit is of much larger radix (16-bits or 65536 is common) than the digits to the right, as this allows a large first-level table of which there is only one instance.
Each time another group of address bits is consumed, the look up descends into a deeper level (L2, L3, etc.) of the trie. By way of example, suppose a trie had only three levels; in this case, 16 bits might be consumed for indexing the L1 table, 8 bits for indexing each L2 subtable, of which there may be many instances, and the last 8-bits of the 32-bit address for indexing each L3 subtable. Different breakdowns of IP addresses into levels of the trie are possible, but a 16/8/8 split of bits has proven effective with “real” IP route data.
Whilst radix tries offer fast lookups, for example at most three lookups (for L1, L2, and L3) per 32-bit address, they suffer the disadvantage of being very large compared to the amount of data they hold. One of the reasons for this is a phenomenon called “prefix expansion”. Prefix expansion is caused by taking prefixes whose length does not neatly fit the L1, L2, etc. breakdown and expanding them artificially into replicated entries that can be indexed directly given the fixed structure. For example, a 21-bit address prefix does not fit the 24-bit prefix located at L2 for a 16/8-bit L1/L2 structure, hence a single 21-bit prefix is replicated eight times to expand it to eight 24-bit prefixes. This expansion phenomenon particularly affects the economics of placing radix tries in fast memories, such as costly Static Random Access Memory (SRAM).
There is a need for methods and systems that compress arrays, such as radix tries, without affecting the speed of lookups. There is also a need to provide methods and systems that permit Internet routers, and similar devices, to exploit the performance advantage of SRAM while minimizing hardware costs.